package uestc.lj.midPromotion.compressedarray;

/**
 * 矩阵数组中最大的子矩阵和
 * @Author:Crazlee
 * @Date:2021/12/3
 */
public class Code02_SubMatrixMaxSum {
	public static int maxSum(int[][] arr) {
		if (arr == null || arr.length == 0 || arr[0].length == 0) {
			return 0;
		}
		int max = Integer.MIN_VALUE;
		int cur = 0;
		int[] s = null;
		for (int i = 0; i < arr.length; i++) {
			s = new int[arr[0].length];
			for (int j = i; j < arr.length; j++) {
				cur = 0;
				for (int k = 0; k < s.length; k++) {
					s[k] += arr[j][k];
					cur += s[k];
					max = Math.max(max, cur);
					cur = Math.max(0, cur);
				}
			}
		}
		return max;
	}

	public static void main(String[] args) {
		int[][] matrix = {{-90, 48, 78}, {64, -40, 64}, {-81, -7, 66}};
		System.out.println(maxSum(matrix));

	}
}
